package first

import "math"

/*
	给你一个整数数组arr 和一个整数值target。

	请你在 arr中找 两个互不重叠的子数组且它们的和都等于target。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

	请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1。

	示例 1：

	输入：arr = [3,2,2,4,3], target = 3
	输出：2
	解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。
	示例 2：

	输入：arr = [7,3,4,7], target = 7
	输出：2
	解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。
	示例 3：

	输入：arr = [4,3,2,6,2,3,4], target = 6
	输出：-1
	解释：我们只有一个和为 6 的子数组。
	示例 4：

	输入：arr = [5,5,4,4,5], target = 3
	输出：-1
	解释：我们无法找到和为 3 的子数组。
	示例 5：

	输入：arr = [3,1,1,1,5,1,2,1], target = 3
	输出：3
	解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。

	提示：

	1 <= arr.length <= 10^5
	1 <= arr[i] <= 1000
	1 <= target <= 10^8

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

func MinSumOfLengths(arr []int, target int) int {
	return minSumOfLengths(arr, target)
}

func minSumOfLengths(arr []int, target int) int {
	if len(arr) <= 1 {
		return -1
	}
	dp := make([]int, len(arr)+1)
	if arr[0] == target {
		dp[1] = 1
	}
	l, r := 0, 1
	length := math.MinInt32
	sum := 0
	for l < len(arr) {
		sum += arr[r-1]
		for sum > target {
			sum -= arr[l]
			l++
		}
		if sum == target {
			dp[r] = min(dp[r-1], r-l)
		} else {
			dp[r] = dp[r-1]
			r++
		}
	}
	if length == math.MinInt32 {
		return -1
	}
	return length
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}
